#include "array/two_sum.h"

#include "hash_table/hash_table.h"

bool twoSum(const int arr[], const int n, const int sum, size_t& first, size_t& second)
{
    first = second = SIZE_MAX;

    if (n <= 1)
        return false;

    int left, right;
    left = 0;
    right = n - 1;

    bool found = false;

    while (left < right)
    {
        if ((arr[left] + arr[right]) < sum)
            left++;
        else if ((arr[left] + arr[right]) > sum)
            right--;
        else
        {
            found = true;
            break;
        }
    }

    if (found)
    {
        first = left;
        second = right;
    }

    return found;
}

bool twoSumBruteForce(const int arr[], const int n, const int sum, size_t& first, size_t& second)
{
    first = second = SIZE_MAX;

    if (n <= 1)
        return false;

    bool found = false;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] + arr[j]) == sum)
            {
                found = true;
                first = i;
                second = j;
                break;
            }
        }
    }

    return found;
}

bool twoSumHashTable(const int arr[], const int n, const int sum, size_t& first, size_t& second)
{
    first = second = SIZE_MAX;

    if (n <= 1)
        return false;

    bool found = false;

    HashTable<int /*值*/, size_t> table;

    for (int i = 0; i < n; i++)
    {
        int complement = sum - arr[i];
        size_t idx = SIZE_MAX;
        if (table.find(complement, idx))
        {
            first = idx;
            second = i;
            found = true;
            break;
        }
        table.insert(arr[i], i);
    }

    return found;
}